// 快排
var data = new Array()
while (data.length < 250000) {
	data.push(Math.floor(Math.random() * 200000))
}
console.time()

function QuickSort(arr, num = 0) {
	let len = arr.length
	if ((len == 2 && arr[0] == arr[len - 1]) || len < 2) {
		return arr
	}

	let minArr = new Array()
	let maxArr = new Array()

	maxArr[0] = arr[len - 1]
	for (let i = 0; i < arr.length - 1; i++) {
		if (arr[i] <= maxArr[0]) {
			minArr.push(arr[i])
		} else {
			maxArr.push(arr[i])
		}
	}
	return QuickSort(minArr).concat(QuickSort(maxArr))
}


// 异步   未实现
// function QuickSort(arr, callback) {
// 	setTimeout(() => {
// 		let len = arr.length
// 		if ((len == 2 && arr[0] == arr[len - 1]) || len < 2) {
// 			callback(arr)
// 		}

// 		let minArr = new Array()
// 		let maxArr = new Array()

// 		maxArr[0] = arr[len - 1]
// 		for (let i = 0; i < arr.length - 1; i++) {
// 			if (arr[i] <= maxArr[0]) {
// 				minArr.push(arr[i])
// 			} else {
// 				maxArr.push(arr[i])
// 			}
// 		}

// 		console.log(minArr, maxArr)
// 		QuickSort(minArr, arrI => {
// 			QuickSort(maxArr, arrA => {
// 				callback(arrI.concat(arrA))
// 			})
// 		})
// 	}, 0)
// }

console.log(data)
var a = QuickSort(data)
console.log(a)

// 异步附带
// var a
// QuickSort(data, arr => {
// 	a = arr
// })
// console.log(a)
console.timeEnd()

console.time()
console.log(data.sort((a, b) => a - b))
console.timeEnd()